//给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。 
//
// 
//
// 示例 1: 
//
// 
//输入: n = 13, k = 2
//输出: 10
//解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
// 
//
// 示例 2: 
//
// 
//输入: n = 1, k = 1
//输出: 1
// 
//
// 
//
// 提示: 
//
// 
// 1 <= k <= n <= 109 
// 
// Related Topics 字典树 
// 👍 405 👎 0

package com.cute.leetcode.editor.cn;
public class KThSmallestInLexicographicalOrder {
    public static void main(String[] args) {
        new KThSmallestInLexicographicalOrder().new Solution().findKthNumber(1234, 1234);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 本质是10叉树的前序遍历，取第K个数字出来
         * 假设所有相同位数的10叉树在同一层上，那么先序遍历就是字典序排序
         * 从cur=1开始进行遍历，计算以cur为根且<=n的节点的个数返回
         * 根据返回的节点数进行遍历方向的选择：
         *  如果总结点数<=k，说明节点数够用，向右寻找(+1)，否则去向下去找（*10）
         */
        public int findKthNumber(int n, int k) {
            int ans = 1;
            while (k > 1){
                //首先传入的是1
                int count = getCount(ans, n);
                if (count < k){// 此时说明这个当前ans前缀都可以跳过了
                    //比如1起始时如果count<k则跳过所有1开头的数，开始以2开头
                    k -= count;
                    ans++;
                }else {
                    k--;// 字典升序时1和10只差了一个数，所以k--
                    ans *= 10;// 说明在这个前缀到limit之间，需要将ans放大10倍以判断下个前缀
                }
            }
            //当k=1时ans就是答案了
            return ans;
        }
        /**
         * @param prefix 前缀
         * @param limit 最大值
         * @return 返回以x为前缀在limit内的个数
         */
        public int getCount(int prefix, int limit){
            // 全部转换为long是为了防止整数溢出
            long cur = prefix;
            long next = cur + 1;
            // 保留当前前缀开始的总数
            int totalNodes = 0;

            /**
             * 例如初始时cur = 1, next = 2, limit = 12
             * 第一次会添加1个节点，cur = 10, next = 20;
             * 第二次会添加3个节点，之后返回共4个节点，即1 10 11 12
             * 计数时是按照层来计算的，比如1 2 3 ...9 在第一层，10 11 20 ...在第二层，100在第三层...
             * 如果next没超过limit，直接添加一层节点，否则部分添加
             */
            while (cur <= limit){
                totalNodes += Math.min(limit - cur + 1, next - cur);
                cur *= 10;
                next *= 10;
            }
            return totalNodes;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}